package personal_exercise;

import model.TreeNode;

import java.util.*;

public class Demo3 {

    // NC114 旋转字符串
    public boolean solve (String A, String B) {
        if (A.length() != B.length()) return false;
        int n = A.length();
        A = A + A;
        for (int i = 0; i < n; i++) {
            if (A.charAt(i) == B.charAt(0)) {
                int x = i, y = 0;
                while (y < n && A.charAt(x) == B.charAt(y)) {
                    x++; y++;
                }
                if (y == n) return true;
            }
        }
        return false;
    }


    // DP18 滑雪
    private static int[][] memo;
    private static boolean[][] vis;
    private static int n, m;
    private static int[] dx = {0,0,1,-1};
    private static int[] dy = {1,-1,0,0};
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                arr[i][j] = in.nextInt();
        }

        memo = new int[n][m];
        vis = new boolean[n][m];
        // 递归 + 记忆化搜索
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = Math.max(res, dfs(arr, i, j));
            }
        }
        System.out.println(res);
    }
    private static int dfs(int[][] arr, int i, int j) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        vis[i][j] = true;

        int max = 1;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && arr[i][j] > arr[x][y] && !vis[x][y]) {
                max = Math.max(max, dfs(arr, x, y) + 1);
            }
        }
        // 存储结果
        memo[i][j] = max;
        vis[i][j] = false;
        return memo[i][j];
    }



    // DP40 小红取数
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextLong();

        // dp[i][j]: 从前 i 个数中选取若干个数,使得其总和 sum % 3 == j 的最大和
        long[][] dp = new long[n + 1][k];
        for (int j = 1; j < k; j++) dp[0][j] = (long)-1e16;

        for (int i = 1; i <= n; i++) {
            long modNum = arr[i - 1] % k;
            for (int j = 0; j < k; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(int)(j - modNum + k) % k] + arr[i - 1]);
            }
        }

        if (dp[n][0] == 0) {
            System.out.println(-1);
        } else {
            System.out.println(dp[n][0]);
        }
    }



    // DP16 合唱队形
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        // f[i]: 以 i 为结尾的最长上升子序列的长度
        // g[i]: 以 i 为结尾的最长上升子序列的长度(从右往左)
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            g[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) g[i] = Math.max(g[i], g[j] + 1);
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, f[i] + g[i] - 1);
        }
        System.out.println(n - res);
    }



    //
//    private int[] dx = {0,0,1,-1};
//    private int[] dy = {1,-1,0,0};
    public int[][] flipChess (int[][] A, int[][] f) {
        for (int[] arr : f) {
            int i = arr[0] - 1, j = arr[1] - 1;
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < 4 && y >= 0 && y < 4) {
                    A[x][y] = Math.abs(A[x][y] - 1);
                }
            }
        }
        return A;
    }



    //
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        // dp[i]: 以 i 为结尾的道路部分,所能获得的最大饱食度
        long[] dp = new long[n];
        dp[2] = arr[1];

        for (int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 3] + arr[i -1]);
        }
        System.out.println(dp[n - 1]);
    }




    //
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        boolean[] vis = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        vis[0] = true;
        int time = 0;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                int index = q.poll();
                int maxStep = arr[index];
                if (maxStep > 0) {
                    if (n - 1 - index <= maxStep) {
                        System.out.println(time + 1);
                        return;
                    }
                    for (int i = 1; i <= maxStep; i++) {
                        int pos = index + i;
                        if (!vis[pos]) {
                            q.offer(pos);
                            vis[pos] = true;
                        }
                    }
                } else {
                    for (int i = index + maxStep; i >= 0; i--) {
                        if (!vis[i]) {
                            q.offer(i);
                            vis[i] = true;
                        }
                    }
                }
            }
            time++;
        }
        System.out.println(-1);
    }





    // 93. 复原 IP 地址
    private StringBuilder path;
    private List<String> res;
//    private int n;

    public List<String> restoreIpAddresses(String s) {
        path = new StringBuilder();
        res = new ArrayList<>();
        n = s.length();
        dfs(s, 0, 0);
        return res;
    }
    private void dfs(String s, int pos, int count) {
        if (pos == n || count == 4) {
            if (pos == n && count == 4) res.add(path.toString());
            return;
        }

        for (int i = 1; i <= 3; i++) {
            // 枚举 1 ~ 3位IP地址的情况
            if (pos + i > n) break;
            String ip = s.substring(pos, pos + i);
            int num = Integer.parseInt(ip);
            // 对 3 位的 IP地址做特殊判断
            if (i == 3 && num > 255) continue;
            // 1 - 3 位的 IP 地址都应该符合下述条件
            if (i != 1 && (num < Math.pow(10, i - 1) || num >= Math.pow(10, i))) continue;

            path.append(ip);
            if (count < 3) path.append('.');
            dfs(s, pos + i, count + 1);
            if (count < 3) path.deleteCharAt(path.length() - 1);
            path.delete(path.length() - i, path.length());
        }
    }



    // 最大差值
    public int getDis (int[] A, int n) {
        int min = A[0], cur = 0;
        int res = Integer.MIN_VALUE;
        while (cur < n) {
            res = Math.max(res, A[cur] - min);
            if (A[cur] < min) min = A[cur];
            cur++;
        }
        return res;
    }



    // 兑换零钱
    public static void main6(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), aim = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();
        // 一维完全背包
        int[] dp = new int[aim + 1];
        for (int i = 1; i <= aim; i++) {
            dp[i] = 0X3f3f3f3f;
        }

        for (int i = 0; i < n; i++) {
            for (int j = arr[i]; j <= aim; j++) {
                dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
            }
        }
        if(dp[aim] >= 0X3f3f3f3f) dp[aim] = -1;
        System.out.println(dp[aim]);
    }


    // 小红的子串
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), l = in.nextInt(), r = in.nextInt();
        char[] arr = in.next().toCharArray();

        System.out.println(find(r, arr) - find(l - 1, arr));
    }
    // 找出字母种类数量为 1 ~ n 的子串的个数
    private static long find(int x, char[] arr) {
        int kinds = 0;                    // 统计字母种类出现的个数
        int[] count = new int[128];     // 统计每个字母出现的次数
        int left = 0, right = 0;
        long res = 0;
        for (int n = arr.length; right < n; right++) {
            char ch = arr[right];
            if (count[ch]++ == 0) kinds++;

            while (kinds > x) {
                char tmp = arr[left++];
                if (--count[tmp] == 0) kinds--;
            }
            res += right - left + 1;
        }
        return res;
    }



    // BM22 比较版本号
    public static int compare (String version1, String version2) {
        String[] strs1 = version1.split("\\."), strs2 = version2.split("\\.");
        int n = strs1.length, m = strs2.length;
        int i = 0, j = 0;
        for (; i < n && j < m; i++, j++) {
            int num1 = Integer.parseInt(strs1[i]);
            int num2 = Integer.parseInt(strs2[j]);
            if (num1 > num2) return 1;
            else if (num1 < num2) return -1;
        }
        while (i < n) {
            if (Integer.parseInt(strs1[i]) > 0) return 1;
        }
        while (j < m) {
            if (Integer.parseInt(strs2[j]) > 0) return -1;
        }
        return 0;
    }



    //  575. 分糖果
    public int distributeCandies(int[] candyType) {
        boolean[] flag = new boolean[200001];
        int kinds = 0, n = candyType.length;
        for (int x : candyType) {
            if (!flag[x + 100000]) kinds++;
            flag[x + 100000] = true;
        }
        return Math.min(kinds, n / 2);
    }



    // 99. 恢复二叉搜索树
    private TreeNode prev;          // 中序遍历的前驱节点
    private TreeNode flag;          // 标记第一次比当前遍历节点值大的前驱节点
    private boolean exchange;       // 标记是否将节点位置改正

    public void recoverTree(TreeNode root) {
        inorder(root);
        // 若中序遍历过程没有交换节点，则证明该 flag节点 应为中序遍历的最后一个结点
        if (!exchange) {
            int temp = flag.val;
            flag.val = prev.val;
            prev.val = temp;
        }
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        // 剪枝操作：若已经发生交换，无需进行后续遍历
        if (!exchange) inorder(root.left);

        // 第一次(即 flag == null)比当前节点大的前驱节点即被错误交换的节点
        if (prev != null && prev.val > root.val && flag == null) flag = prev;

        // 未执行交换操作才执行以下逻辑
        if (flag != null && flag.val < root.val && !exchange) {
            int temp = flag.val;
            flag.val = prev.val;
            prev.val = temp;
            exchange = true;
            return;
        }
        prev = root;
        // 剪枝操作：若已经发生交换，无需进行后续遍历
        if (!exchange) inorder(root.right);
    }
}
